package basic.courseLearn02.problem;

import org.junit.Test;
import basic.utils.CommonUtil;

public class SmallSum {


    @Test
    public void test(){
        executeCheckAlgorithm(1_0000,1000,1000);
    }

    //小和问题，当一个数左边比当前数小的数加起来，总和叫做小和，求一个数组的小和
    //解决思路：小河问题等价于，一个数右边比自己大的个数，在乘以本身，对所有的数依次求和
    //可以利用归并思想，在合并的过程中记录比自己大的个数
    public int smallSum(int[] arr,int leftIndex,int rightIndex){
        if (leftIndex == rightIndex){   //该区域只有一个数
            return 0;
        }
        //得到中点
        int center = leftIndex +((rightIndex-leftIndex)>>1);
        return smallSum(arr , leftIndex, center)+
                smallSum(arr , center+1, rightIndex)+
                merge(arr,leftIndex,center,rightIndex);
    }


    //合并操作，在合并的过程中统计小和
    public int merge(int[] arr,int leftIndex,int center,int rightIndex){
        int i=leftIndex,j=center+1,k=0;
        int sum=0;
        int[] result = new int[rightIndex-leftIndex+1];
        //合并操作
        while(i<=center && j<=rightIndex){
            if (arr[i]<arr[j]){           //arr1小于arr2情况
                sum+=arr[i]*(rightIndex-j+1);
                result[k++]=arr[i++];
            }else{     //arr1大于等于arr2情况
                result[k++]=arr[j++];
            }
        }
        //左侧未合并完
        while(i<=center){
            result[k++]=arr[i++];
        }
        //右侧未合并完
        while(j<=rightIndex){
            result[k++]=arr[j++];
        }
        for (int l = leftIndex; l <= rightIndex; l++) {
            arr[l]=result[l-leftIndex];
        }
        return sum;
    }

    //算法b
    public int rightAlgorithm(int[] arr){
        int sum=0;
        for (int i=0;i<arr.length;i++){
            for (int j=0;j<i;j++){
                if (arr[j]<arr[i]){
                    sum+=arr[j];
                }
            }
        }
        return sum;
    }

    //核实操作
    public void executeCheckAlgorithm(int loopNum, int size, int limit){
        boolean right =true;
        int[] arr;
        for (int i = 0; i < loopNum; i++) {
//        1.生成数组result_a
            arr= CommonUtil.generateArrays(size,limit);

//        2.对数组a使用方式1求最大值
            int max1= rightAlgorithm(arr);

//        3.对数组a使用方式2求最大值
            int max2=smallSum(arr,0,arr.length-1);

//        4.核实比对两数组
            if (max1!=max2){
                System.out.println("oh my god");
                right=false;
                break;
            }
        }
        if (right){
            System.out.println("very good");
        }
    }


}
